#include "particao.h"

Particao::Particao(Grafo *grf, int tot, double fB){
  
  grafo = grf;
  fatorBalanceamento = fB;
  n = grf->adj.size();
  total = tot;
  
  pesoParticao[0] = 0;
  pesoParticao[1] = 0;
  
  particao = (int *) malloc(sizeof(int) * (n + 1));
  particaoOtima = (int *) malloc(sizeof(int) * (n + 1));
}

void Particao::geraParticaoAleatoria(void){

  int nA;
  int p;
  
  for(int i = 0; i < n; ++ i){

    //printf(" (%d) ",peso[i]);
    p = rand()%2;
    nA = 0;

    if(pesoParticao[p]+ (*grafo).vPeso[i] <= ceil(fatorBalanceamento * total)){
	particao[i] = p;
	pesoParticao[p] += (*grafo).vPeso[i];
    
    }else{

	p = (p+1)%2;
	
	if(pesoParticao[p]+ (*grafo).vPeso[i] <= ceil(fatorBalanceamento * total)){
	  particao[i] = p;
	  pesoParticao[p] += (*grafo).vPeso[i];
	
	}else nA = 1;

    }

    if(nA == 1){
      particao[i] = (pesoParticao[0] < pesoParticao[1] ? 0 : 1);
      pesoParticao[particao[i]] += (*grafo).vPeso[i];
    }

    //printf("%d ", particao[i]);

  }

  grafo->pOtima = particao;

  //printf("\n");

  //printf("pesoA = %d, pesoB = %d\n", pesoParticao[0], pesoParticao[1]);
  
}

void Particao::geraParticaoOtima(void){

  
  particao[0] = 0;
  particaoOtima[n] = n*n;
  
  pesoParticao[0] = (*grafo).vPeso[0];
  
  
  
  bck_pOtima(1);
  
  if(particaoOtima[n] == n*n){
    printf("Nao eh possivel encontrar uma particao para esse grafo com fb = %f\n", fatorBalanceamento);
    exit(1);
  }
  
  grafo->pOtima = particaoOtima;

}

void Particao::bck_pOtima(int i){

  
	if(i == n){

		particao[n] = 0;		

		for(int k = 0; k < n; ++k){

			for(unsigned int j = 0; j < (*grafo).adj[k].size(); ++j){
				if(k < (*grafo).adj[k][j].v && particao[(*grafo).adj[k][j].v] != particao[k]){ 
					particao[n]+= (*grafo).adj[k][j].peso;
				}
			}
		}

		if(particao[n] < particaoOtima[n]) atribuiParticaoOtima();

	}else{

		for(int p = 0; p < 2; ++p){
			if(pesoParticao[p] + (*grafo).vPeso[i] <= ceil(fatorBalanceamento * total)){

				particao[i] = p;
				pesoParticao[p] += (*grafo).vPeso[i];

				bck_pOtima(i+1);

				pesoParticao[p] -= (*grafo).vPeso[i];

			}
		}

	}
}


void Particao::atribuiParticaoOtima(void){

  for(int i = 0; i <= n; ++ i){
    particaoOtima[i] = particao[i];
  }  
  
}
